home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_high.lha / LEDA-3.1c-high / man / graph_alg.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  11.8 KB  |  324 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.12 Graph Algorithms} 
  4. \bigskip
  5.  
  6. This sections gives a summary of the graph algorithms contained in LEDA.
  7. All algorithms are generic, i.e., they accept instances of any user defined
  8. parameterized graph type $GRAPH\<vtype,etype\>$ as arguments.
  9.  
  10. \bigskip
  11. {\bf 5.12.1 Basic Algorithms}
  12.  
  13. \bigskip
  14. $\bullet$ {\bf Topological Sorting}
  15.  
  16. $bool$ TOPSORT($graph\&\ G,\ node\_array\<int\>\&\ ord$)
  17.  
  18. TOPSORT takes as argument a directed graph $G(V,E)$. It sorts $G$ topologically 
  19. (if $G$ is acyclic) by computing for every node $v \in V$ an integer $ord[v]$ 
  20. such that $1\le ord[v]\le |V|$ and $ord[v] < ord[w]$ for all edges 
  21. $(v,w) \in E$. TOPSORT returns true if $G$ is acyclic and false otherwise.
  22.  
  23. The algorithm ([Ka62]) has running time $O(|V|+|E|)$.
  24.  
  25.  
  26.  
  27. \bigskip
  28. $\bullet$ {\bf Depth First Search}
  29.  
  30. $list\<node\>$  DFS($graph\&\ G,\ node\ s,\ node\_array\<bool\>\&\ reached$) 
  31.  
  32. DFS takes as argument a directed graph $G(V,E)$, a node $s$ of $G$ and a 
  33. node\_array $reached$ of boolean values. It performs a depth first search 
  34. starting at $s$ visiting all reachable nodes $v$ with $reached[v]$ = false. 
  35. For every visited node $v$ $reached[v]$ is changed to true. DFS returns the 
  36. list of all reached nodes.
  37.  
  38. The algorithm ([T72]) has running time $O(|V|+|E|)$.
  39.  
  40.  
  41. \bigskip
  42. \cleartabs
  43. \+$list\<edge\>$  DFS\_NUM($graph\&\ G$, &$node\_array\<int\>\&\ dfsnum$,\cr
  44. \+                                     &$node\_array\<int\>\&\ compnum$)\cr
  45.  
  46. DFS\_NUM takes as argument a directed graph $G(V,E)$. It performs a 
  47. depth first search of $G$ numbering the nodes of $G$ in two different ways. 
  48. $dfsnum$ is a numbering with respect to the calling time and $compnum$ a 
  49. numbering with respect to the completion time of the recursive calls. DFS\_NUM 
  50. returns a depth first search forest of $G$ (list of tree edges).
  51.  
  52. The algorithm ([T72]) has running time $O(|V|+|E|)$.
  53.  
  54.  
  55. \bigskip
  56. $\bullet$ {\bf Breadth First Search}
  57.  
  58. $list\<node\>$   BFS($graph\&\ G,\ node\ s,\ node\_array\<int\>\&\ dist$)
  59.  
  60. BFS takes as argument a directed graph $G(V,E)$ and a node $s$ of $G$. It 
  61. performs a breadth first search starting at $s$ computing for every visited 
  62. node $v$ the distance $dist[v]$ from $s$ to $v$. BFS returns the list of all 
  63. reached nodes.
  64.  
  65. The algorithm ([M84]) has running time $O(|V|+|E|)$.
  66.  
  67. \bigskip
  68. $\bullet$ {\bf Connected Components}
  69.  
  70. $int$   COMPONENTS($ugraph\&\ G,\ node\_array\<int\>\&\ compnum$)
  71.  
  72. COMPONENTS takes an undirected graph $G(V,E)$ as argument and computes 
  73. for every node $v\in V$ an integer $compnum[v]$ from $[0\dots c-1]$ where
  74. $c$ is the number of connected components of $G$ and 
  75. $v$ belongs to the $i$-th connected component iff $compnum[v] = i$.
  76. COMPONENTS returns $c$.
  77.  
  78. The algorithm ([M84]) has running time $O(|V|+|E|)$.
  79.  
  80.  
  81. \bigskip
  82. $\bullet$ {\bf Strong Connected Components}
  83.  
  84. $int$   STRONG\_COMPONENTS($graph\&\ G,\ node\_array\<int\>\&\ compnum$)
  85.  
  86. STRONG\_COMPONENTS takes a directed graph $G(V,E)$ as argument and computes for 
  87. every node $v\in V$ an integer $compnum[v]$ from $[0\dots c-1]$ where
  88. $c$ is the number of strongly connected components of $G$ and
  89. $v$ belongs to the $i$-th strongly connected component iff $compnum[v] = i$.
  90. STRONG\_COMPONENTS returns $c$.
  91.  
  92. The algorithm ([M84]) has running time $O(|V|+|E|)$.
  93.  
  94. \bigskip
  95. $\bullet$ {\bf Transitive Closure}
  96.  
  97. $graph$ TRANSITIVE\_CLOSURE($graph\&\ G$)
  98.  
  99. TRANSITIVE\_CLOSURE takes a directed graph $G(V,E)$ as argument and computes the 
  100. transitive closure of $G(V,E)$. It returns a directed graph $G\'(V\',E\')$ with
  101. $V\' = V$ and $(v,w) \in E\'  \Leftrightarrow$ there is a path form
  102. $v$ to $w$ in $G$.
  103.  
  104. The algorithm ([GK79]) has running time $O(|V|\cdot |E|)$.
  105.  
  106.  
  107.  
  108.  
  109.  
  110. \bigskip
  111. {\bf 5.12.2 Network Algorithms}
  112.  
  113. Most of the following network algorithms are overloaded. They work
  114. for both integer and real valued edge costs.
  115.  
  116. \bigskip
  117. $\bullet$ {\bf Single Source Shortest Paths }
  118.  
  119. \medskip
  120. \cleartabs
  121. \+$void$ DIJKSTRA($graph\&\ G,\ node\ s$,\ edge\_array\<int\>\ $cost$,
  122.                                           &$node\_array\<int\>$\ \ \ &$dist$,\cr
  123. \+                                        &$node\_array\<edge\>$     &$pred$)\cr
  124. \medskip
  125. \cleartabs
  126. \+$void$ DIJKSTRA($graph\&\ G,\ node\ s$,\ edge\_array\<double\>\ $cost$,
  127.                                           &$node\_array\<double\>$\ \ \ &$dist$,\cr
  128. \+                                        &$node\_array\<edge\>$     &$pred$)\cr
  129.  
  130. DIJKSTRA takes as arguments a directed graph G(V,E), a source node $s$ and an 
  131. edge\_array $cost$ giving for each edge in $G$ a non-negative cost. It 
  132. computes for each node $v$ in $G$ the distance $dist[v]$ from $s$ (cost of the 
  133. least cost path from $s$ to $v$) and the predecessor edge $pred[v]$ in the 
  134. shortest path tree.
  135.  
  136. The algorithm ([Di59,FT87]) has running time $O(|E|+|V|\log |V|)$.
  137.  
  138. \bigskip
  139. \cleartabs
  140. \+$bool$ BELLMAN\_FORD($graph\&\ G,\ node\ s$, 
  141.                        &$edge\_array\<int\>$\ \ &$cost$,\cr
  142. \+                     &$node\_array\<int\>$    &$dist$,\cr
  143. \+                     &$node\_array\<int\>$    &$pred$)\cr
  144. \medskip
  145. \cleartabs
  146. \+$bool$ BELLMAN\_FORD($graph\&\ G,\ node\ s$, 
  147.                        &$edge\_array\<double\>$\ \ &$cost$,\cr
  148. \+                     &$node\_array\<double\>$    &$dist$,\cr
  149. \+                     &$node\_array\<edge\>$    &$pred$)\cr
  150.  
  151. BELLMAN\_FORD takes as arguments a graph G(V,E), a source node $s$ and an 
  152. edge\_array $cost$ giving for each edge in $G$ a real (integer) cost. It 
  153. computes for each node $v$ in $G$ the distance $dist[v]$ from $s$ (cost of 
  154. the least cost path from $s$ to $v$) and the predecessor edge $pred[v]$ in 
  155. the shortest path tree. BELLMAN\_FORD returns false if there is a negative
  156. cycle in $G$ and true otherwise
  157.  
  158. The algorithm ([Be58]) has running time $O(|V|\cdot|E|)$.
  159.  
  160. \bigskip
  161. $\bullet$ {\bf All Pairs Shortest Paths }
  162.  
  163. \cleartabs
  164. \+$void$ ALL\_PAIRS\_SHORTEST\_PATHS($graph\&\ G$,
  165.                                      &$edge\_array\<int\>$\&\ \ \ &$cost$,\cr
  166. \+                                   &$node\_matrix\<int\>$\&  &$dist$)\cr
  167. \medskip
  168. \cleartabs
  169. \+$void$ ALL\_PAIRS\_SHORTEST\_PATHS($graph\&\ G$,
  170.                                      &$edge\_array\<double\>$\&\ \ \ &$cost$,\cr
  171. \+                                   &$node\_matrix\<double\>$\&  &$dist$)\cr
  172.  
  173. ALL\_PAIRS\_SHORTES\_PATHS takes as arguments a graph $G(V,E)$ and an 
  174. edge\_array $cost$ giving for each edge in $G$ a real (integer) valued cost. 
  175. It computes for each node pair $(v,w)$ of $G$ the distance $dist(v,w)$ from 
  176. $v$ to $w$ (cost of the least cost path from $v$ to $w$).
  177.  
  178. The algorithm ([Be58,Fl62]) has running time $O(|V|\cdot|E| + |V|^2 \log|V|)$.
  179.  
  180. \bigskip
  181. $\bullet$ {\bf Maximum Flow }
  182.  
  183. \medskip
  184. \cleartabs
  185. \+$int$ MAX\_FLOW($graph\&\ G,\ node\ s,\ node\ t$, 
  186.                                                &$edge\_array\<int\>\&\ cap$,\cr
  187. \+                                             &$edge\_array\<int\>\&\ flow$)\cr
  188. \medskip
  189. \+$int$ MAX\_FLOW($graph\&\ G,\ node\ s,\ node\ t$, 
  190.                                                &$edge\_array\<double\>\&\ cap$,\cr
  191. \+                                             &$edge\_array\<double\>\&\ flow$)\cr
  192.  
  193. MAX\_FLOW takes as arguments a directed graph $G(V,E)$, a source node $s$, a 
  194. sink node $t$ and an edge\_array $cap$ giving for each edge in $G$ a capacity. 
  195. It computes for every edge $e$ in $G$ a flow $flow[e]$ such that the total 
  196. flow from $s$ to $t$ is maximal and $flow[e] \le cap[e]$ for all edges $e$. 
  197. MAX\_FLOW returns the total flow from $s$ to $t$.
  198.  
  199. The algorithm ([GT88]) has running time $O(|V|^3)$.
  200.  
  201. \bigskip
  202. $\bullet$ {\bf Maximum Cardinality Matching}
  203.  
  204. $list\<edge\>$ MAX\_CARD\_MATCHING($graph\&\ G$) 
  205.  
  206. MAX\_CARD\_MATCHING($G$) computes a maximum cardinality matching of $G$, i.e., 
  207. a maximal set of edges $M$ such that no two edges in $M$ share an end point.
  208. It returns $M$ as a list of edges.
  209.  
  210. The algorithm ([E65,T83]) has running time $O(|V|\cdot|E|\cdot\alpha(|E|))$.
  211.  
  212.  
  213.  
  214. \bigskip
  215. $\bullet$ {\bf Maximum Cardinality Bipartite Matching}
  216.  
  217. \medskip
  218. \cleartabs
  219. \+$list\<edge\>$ MAX\_CARD\_BIPARTITE\_MATCHING($graph\&\ G$, 
  220.                                               &$list\<node\>\&\ A$,\cr
  221. \+                                            &$list\<node\>\&\ B$)\cr
  222.  
  223. MAX\_CARD\_BIPARTITE\_MATCHING takes as arguments a directed graph $G(V,E)$ and
  224. two lists $A$ and $B$ of nodes. All edges in $G$ must be directed from nodes
  225. in $A$ to nodes in $B$. It returns a maximum cardinality matching of $G$.
  226.  
  227. The algorithm ([HK75]) has running time $O(|E|\sqrt{|V|})$.
  228.  
  229. \bigskip
  230. $\bullet$ {\bf Maximum Weight Bipartite Matching}
  231.  
  232. \cleartabs
  233. \+$list\<edge\>$ MAX\_WEIGHT\_BIPARTITE\_MATCHING(&$graph\&\ G$,\cr 
  234. \+                                              &$list\<node\>\&\ A$,\cr
  235. \+                                              &$list\<node\>\&\ B$,\cr
  236. \+                                              &$edge\_array\<int\>\&\ weight$)\cr
  237.  
  238. \cleartabs
  239. \+$list\<edge\>$ MAX\_WEIGHT\_BIPARTITE\_MATCHING(&$graph\&\ G$,\cr 
  240. \+                                              &$list\<node\>\&\ A$,\cr
  241. \+                                              &$list\<node\>\&\ B$,\cr
  242. \+                                              &$edge\_array\<double\>\&\ weight$)\cr
  243.  
  244. MAX\_WEIGHT\_BIPARTITE\_MATCHING takes as arguments a directed graph $G$, 
  245. two lists $A$ and $B$ of nodes and an edge\_array giving for each edge an 
  246. integer (real) weight. All edges in $G$ must be directed from nodes in $A$ 
  247. to nodes in $B$. 
  248. It computes a maximum weight bipartite matching of $G$, i.e., a set of edges $M$
  249. such that the sum of weights of all edges in $M$ is maximal and no two edges 
  250. in $M$ share an end point. MAX\_WEIGHT\_BIPARTITE\_MATCHING returns $M$ as a 
  251. list of edges.
  252.  
  253. The algorithm ([FT87]) has running time $O(|V|\cdot |E|)$.
  254.  
  255. \bigskip
  256. $\bullet$ {\bf Spanning Tree}
  257.  
  258. \medskip
  259. $list\<edge\>$ SPANNING\_TREE($ugraph\&\ G$)
  260.  
  261. SPANNING\_TREE takes as argument an undirected graph $G(V,E)$. It computes
  262. a spanning tree $T$ of $G$, SPANNING\_TREE returns the list of edges of $T$.
  263.  
  264. The algorithm ([M84]) has running time $O(|V|+|E|)$.
  265.  
  266. \bigskip
  267. $\bullet$ {\bf Minimum Spanning Tree}
  268.  
  269. $list\<edge\>$ MIN\_SPANNING\_TREE($ugraph\& G,\ edge\_array\<int\>\&\ cost$)
  270. \medskip
  271. $list\<edge\>$ MIN\_SPANNING\_TREE($ugraph\& G,\ edge\_array\<double\>\&\ cost$)
  272.  
  273. MIN\_SPANNING\_TREE takes as argument an undirected graph $G(V,E)$ and an edge\_array
  274. $cost$ giving for each edge an integer cost. It computes a minimum spanning 
  275. tree $T$ of $G$, i.e., a spanning tree such that the sum of all edge costs
  276. is minimal. MIN\_SPANNING\_TREE returns the list of edges of $T$.
  277.  
  278. The algorithm ([Kr56]) has running time $O(|E|\log|V|)$.
  279.  
  280.  
  281. \bigskip
  282. {\bf 5.12.3 Algorithms for Planar Graphs}
  283.  
  284. \bigskip
  285. $\bullet$ {\bf Planarity Test}
  286.  
  287. $bool$ PLANAR($graph\& G$)
  288.  
  289. PLANAR takes as input a directed graph $G(V,E)$ and performs a planarity test
  290. for $G$. If $G$ is a planar graph it is transformed into a planar map
  291. (a combinatorial embedding such that the edges in all adjacency lists 
  292. are in clockwise ordering). PLANAR returns true if $G$ is planar and false
  293. otherwise.
  294.  
  295. The algorithm ([HT74]) has running time $O(|V|+|E|)$.
  296.  
  297. \bigskip
  298. $\bullet$ {\bf Triangulation}
  299.  
  300. $list\<edge\>$ TRIANGULATE\_PLANAR\_MAP($graph\&\ G$)
  301.  
  302. TRIANGULATE\_PLANAR\_MAP takes a directed graph $G$ representing a planar map.
  303. It triangulates the faces of $G$ by inserting additional edges. The list of
  304. inserted edges is returned.
  305.  
  306. The algorithm ([HU89]) has running time $O(|V|+|E|)$.
  307.  
  308. \bigskip
  309. $\bullet$ {\bf Straight Line Embedding}
  310.  
  311. \cleartabs
  312. \+$int$ STRAIGHT\_LINE\_EMBEDDING($graph\&\ G$, &$node\_array\<int\>\&\ xcoord$,\cr
  313. \+                                        &$node\_array\<int\>\&\ ycoord$)\cr
  314.  
  315. STRAIGHT\_LINE\_EMBEDDING takes as argument a directed graph $G$ representing
  316. a planar map. It computes a straight line embedding of $G$ by assigning 
  317. non-negative integer coordinates ($xcoord$ and $ycoord$) in the range 
  318. $0..2(n-1)$ to the nodes. STRAIGHT\_LINE\_EMBEDDING returns the maximal 
  319. coordinate.
  320.  
  321. The algorithm ([Fa48]) has running time $O(|V|^2)$.
  322.  
  323. \vfill\eject
  324.